# Definition for a binary tree node.


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        left = 0
        right = 0

        # 从前序遍历中拿root
        root = TreeNode(preorder.pop(left))

        # 根节点在中序遍历中的索引
        root_index = inorder.index(root.val)

        # 左子树的中序遍历
        left_inorder = inorder[left:root_index]

        # 右子树的中序遍历
        right_inorder = inorder[root_index + 1:-1]

        # 左子树的前序遍历
        left_preorder = []
        for i in range(0, len(left_inorder)):
            left_preorder.append("")

        # 右子树的前序遍历
        right_preorder = []

        # 左子树的根节点
        left_node = TreeNode(preorder.pop(0))

        # 右子树的根节点
        right_node = TreeNode()

        list().split()

        pass

    def buildTree01(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        self.dic = {}
        self.po = preorder

        for i in range(len(inorder)):
            self.dic[inorder[i]] = i

        return self.recur(0, 0, len(inorder) - 1)


    # 前序遍历中根节点的索引pre_root
    # 中序遍历左边界in_left
    # 中序遍历右边界in_right
    def recur(self, pre_root, in_left, in_right):

        if in_left > in_right: 
            # 终止条件：中序遍历为空
            return  


        # 建立当前子树的根节点
        root = TreeNode(self.po[pre_root])  

        # 搜索根节点在中序遍历中的索引，从而可对根节点、左子树、右子树完成划分。
        i = self.dic[self.po[pre_root]]  

        # 开启左子树的下层递归
        root.left = self.recur(pre_root + 1, in_left, i - 1)  

        # 开启右子树的下层递归
        root.right = self.recur(i - in_left + pre_root + 1, i + 1,in_right)  

        # 返回根节点，作为上层递归的左（右）子节点
        return root  
